package com.jacklei.ch12;
/*
* 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

 

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"
 

提示：

1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/multiply-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
public class MultiplyString {
    public static void main(String[] args) {
        MultiplyString m = new MultiplyString();
        System.out.println(m.multiply("123", "456"));
    }
    //失败
    public String multiplyFail(String num1, String num2) {
        StringBuilder ans = new StringBuilder();
        int length = num1.length();
        int pp = length - 1;
        int p = num2.length()-1;
        while (p >=0){
            int c =num2.charAt(p--) - '0';
            StringBuilder zore = new StringBuilder();
            //补零
            for (int i = 0; i < (length - 2 - p); i++) {
                zore.append("0");
            }
            int up = 0;//进位的大小
            StringBuilder add = new StringBuilder();
            StringBuilder copy = new StringBuilder();
            while (pp >= 0){
                int i = c * (num1.charAt(pp--)- '0');
                    add.append(((i % 10) + up) %10);
                    add.append(copy);
                    copy.delete(0,copy.length());
                    copy = copy.append(add);
                    add.delete(0,add.length());
                    up = i/10 + ((i % 10) + up)/10;
            }
            if(up == 0)
                add  = add.append(up).append(copy);
            else
                add= add.append(copy);
            copy.delete(0,copy.length());
            // 两数相加 ans  + temp
            int p3 = ans.length()-1;
            int p4 = add.length()-1;
            StringBuilder temp = new StringBuilder();
            int up2 = 0;
            if(ans.length() == 0){
                ans.append(add);
            }
            while (p3 >= 0 && p4 >= 0) {
                int i = (ans.charAt(p3--) - '0') + (add.charAt(p4--) - '0');

                    temp.append(((i % 10) + up2)%10);
                    temp.append(copy);
                    copy.delete(0,copy.length());
                    copy.append(temp);
                    temp.delete(0,temp.length());
                    up2 = ((i % 10) + up2)%10 + i/10;
            }
            ans.delete(0,ans.length());
            if(up2 == 0) ans = ans.append(temp);
            else
            ans = ans.append(up2).append(temp);
        }
        return  ans.toString();
    }
    public String multiply(String num1, String num2){
        if(num1.equals("0") || num2.equals("0")) return "0";
        String ans = "0";
        int M = num1.length();
        int N = num2.length();
        for (int i = N-1; i >= 0; i--){
            StringBuffer curr = new StringBuffer();
            int add = 0;
            for (int j = N-1; j > i; j--) {
                curr.append(0);
            }
            int y = num2.charAt(i) - '0';
            for (int j = M -1; j >= 0; j--) {
                int x = num1.charAt(j) - '0';
                int product = x * y +add;
                curr.append(product%10);
                add = product/10;
            }
            if (add != 0) {
                curr.append(add % 10);
            }
            ans =addString(ans,curr.reverse().toString());
        }
        return ans;
    }

    private String addString(String num1, String num2) {
        int i = num1.length()-1, j = num2.length()-1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {

            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y +add;
            ans.append(result % 10);
            add = result /10;
            i--;
            j--;
        }
        return ans.reverse().toString();
    }
}
